Many problems of image processing and other processing of two-dimensional data require the rapid generation of two-dimensional Fourier transforms in a form suitable for subsequent electronic processing or utilization. This invention relates to apparatus which performs realtime image processing and which may be implemented with small, light-weight, special-purpose hardware.
In the prior art, two-dimensional Fourier transforms are ordinarily generated either optically or through the use of a digital computer. Both of these methods suffer from severe limitations in many signal-processing applications. A general-purpose digital computer large enough to perform two-dimensional Fourier transforms in real time for may signal-processing applications is large, heavy, expensive, and consumes a large amount of electrical power. Coherent optical two-dimensional Fourier transform implementations are limited by their input-output media and interface poorly with electronic systems.
A third method for performing two-dimensional Fourier transforms is to perform a row by row one-dimensional transform with serial-access hardware, such as that described by Whitehouse, H. J., J. M. Speiser, and R. W. Means, in the article entitled High Speed Serial Access Linear Transform Implementations, presented at the All Applications Digital Computer (AADC) Symposium, Orlando, Florida, 23-25, Jan. 1973. The one-dimensional row transforms are stored, and a column by column one-dimensional transform is performed. This method, however, requires an auxiliary memory to store the one-dimensional transforms of the entire data field. The auxiliary memory tends to be expensive in terms of cost, weight, and power consumption. It is therefore desirable to seek a method of using the one-dimensional serial-access Fourier transform device with a minimum of auxiliary hardware to perform two-dimensional Fourier transforms. The apparatus of this invention accomplishes this task with a minimal amount of hardware.